/*
 * Copyright (C), 2015-2018
 * FileName: Solution219
 * Author:   zhao
 * Date:     2018/9/25 15:14
 * Description: 219. 存在重复元素 II
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredthree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * 〈一句话功能简述〉<br>
 * 〈219. 存在重复元素 II〉
 *
 * @author zhao
 * @date 2018/9/25 15:14
 * @since 1.0.1
 */
public class Solution219 {
  /**************************************
   * 题目

   **************************************/

  /**************************************
   *
   * 想法：
   *    1. HashMap
   *        key数组中的值，value为索引数组
   *        根据key，能取出数据则为true
   *
   *        循环map，
   *          遍历list
   *            再套一个list
   *              判断index是否差值小于等于k
   * 我的做法
   *      超过  %的测试案例
   *
   * 代码执行过程：
   *
   * 总结：
   *
   * ***********************************/
  public boolean containsNearbyDuplicate(int[] nums, int k) {
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
      int n = nums[i];
      ArrayList<Integer> list = map.get(n);
      if (list == null) {
        list = new ArrayList<>();
        list.add(i);
        map.put(n, list);
      } else {
        list.add(i);
      }
    }
    for (Integer key : map.keySet()) {
      ArrayList<Integer> list = map.get(key);
      if (list.size() < 2) {
        continue;
      }
      for (int i = 0; i < list.size(); i++) {
        for (int j = i + 1; j < list.size(); j++) {
          if (list.get(j) - list.get(i) <= k) {
            return true;
          }
        }
      }
    }

    return false;
  }

  /**************************************
   * 比我好的答案 better
   * 直接2个数组嵌套循环
   *    判断ij的差值
   *    判断具体的value值
   * ***********************************/
  public boolean better(int[] nums, int k) {
    for (int i = 0; i < nums.length; i++) {
      for (int j = i + 1; j < nums.length; j++) {
        if (j - i > k) {
          break;
        }
        if (nums[i] == nums[j]) {
          if (j - i <= k) {
            return true;
          }
        }
      }
    }
    return false;

  }

}
